package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class JZ38字符串的排列 {

    /**
     * 输入一个字符串，打印出该字符串中字符的所有排列。
     * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
     *
     * 示例:
     * 输入：s = "abc"
     * 输出：["abc","acb","bac","bca","cab","cba"]
     *  
     * 限制：
     * 1 <= s 的长度 <= 8
     */

    private List<String> list;
    private char[] arr;
    private boolean[] flag;

    //flag是关键
    public String[] permutation(String s) {
        if(s==null||s.length()<1){
            return new String[]{};
        }
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        list=new ArrayList<>();
        this.arr=chars;
        flag=new boolean[s.length()];
        dfs(new StringBuilder());
        String[] result = list.toArray(new String[list.size()]);
        return result;
    }

    private void dfs(StringBuilder path) {
        if(path.length()==this.arr.length){
            list.add(path.toString());
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if(flag[i]||(i>0&&arr[i]==arr[i-1]&&flag[i-1])){
                continue;
            }
            flag[i]=true;
            path.append(arr[i]);
            dfs(path);
            flag[i]=false;
            path.delete(path.length()-1,path.length());
        }

    }

    public static void main(String[] args) {
        JZ38字符串的排列 jz=new JZ38字符串的排列();
        String[] result = jz.permutation("aabb");
        System.out.println(JSON.toJSONString(result));
    }

}
